3D Clipping Addendum
Hello all. This small doc is supposed to explain some things that caused some confusions that some people on IRC told me about. I will give you some explanation for coding boundary spheres for the object and also the boundary-boxes.
Another thing I'd like to mention is that real clipping should be done against 90 degree volume as frenzy explains in his article. It r0x, use it wisely.
Making things clearer
|\
| \
| \
| \
| A********************************************
| *\ *
| * \ *
| * \ *
| * \ O(0,0,0) *
| * \ *
\ * \ *
\ * \ *
\ * \ *
\ B********\***********************************
\ \
\ \
\ \
\ \
\ \
\ \
\ \
\ \
\ \
\COP(0,0,-d)
This ascii is pretty badly drawn, but the plane should go through (0,0,0). Sorry, I just couldn't draw it properly in textmode editor.
A(-160,100,0)
B(-160,-100,0)
O(0,0,0)
From those 3 points you can create the planes.
Another thing. You are supposed to clip against each plane at a time, so first clip against the znear and zfar planes and then against the right, left, top, and bottom planes.
Here's some old example of my code:
// clipping outcodes
int Left_Plane = 1;
int Right_Plane = 2;
int Top_Plane = 4;
int Bot_Plane = 8;
int Near_Plane = 16;
int Far_Plane = 32;
float z_far = -10000;
float z_near = -10.0;
Plane Frustum[6];
void calcoutcode(Vertex *v)
{
int code = 0;
float d = point_plane_dist(&v->vtx, &Frustum[0]); //left plane
if ( d < 0 ) code |= Left_Plane;
d = point_plane_dist(&v->vtx, &Frustum[1]); //right plane
if ( d < 0 ) code |= Right_Plane;
d = point_plane_dist(&v->vtx, &Frustum[2]); //top plane
if ( d < 0 ) code |= Top_Plane;
d = point_plane_dist(&v->vtx, &Frustum[3]); //bot plane
if ( d < 0 ) code |= Bot_Plane;
d = point_plane_dist(&v->vtx, &Frustum[4]); //near plane
if ( d < 0 ) code |= Near_Plane;
v->outcode = code;
}
void point_point_interpolate(Vertex *a, Vertex *b, Vertex *I, float t)
{
// linear interpolation
I->vtx.x = a->vtx.x + t * ( b->vtx.x - a->vtx.x );
I->vtx.y = a->vtx.y + t * ( b->vtx.y - a->vtx.y );
I->vtx.z = a->vtx.z + t * ( b->vtx.z - a->vtx.z );
I->u = a->u + t * ( b->u - a->u );
I->v = a->v + t * ( b->v - a->v );
}
void clip(Polygon *poly, Polygon *poly2, Plane *plane, int outbit)
{
poly2->numvertices = 0;
for (int i = 0; i < poly->numvertices; i++)
{
Vertex v1 = poly->vertices[ i ];
Vertex v2 = poly->vertices[ (i+1) % poly->numvertices ];
int v1c = v1.outcode & outbit;
int v2c = v2.outcode & outbit;
// v1=out //v2=in
// line coming in
if ( (v1c==outbit) && (v2c!=outbit))
{
float d1 = point_plane_dist(&v1.vtx, plane);
float d2 = point_plane_dist(&v2.vtx, plane);
float t = d1 / (float)(d1 - d2);
point_point_interpolate(&v1, &v2,
&poly2->vertices[poly2->numvertices], t);
calcoutcode(&poly2->vertices
[poly2->numvertices++]);
poly2->vertices[poly2->numvertices++]=v2;
}
// v1=in v2=out
// line coming out
if ( (v1c!=outbit) && (v2c==outbit))
{
float d1 = point_plane_dist(&v1.vtx, plane);
float d2 = point_plane_dist(&v2.vtx, plane);
float t = d1 / (float)(d1 - d2);
point_point_interpolate(&v1, &v2,
&poly2->vertices[poly2->numvertices], t);
calcoutcode
(&poly2->vertices[poly2->numvertices++]);
}
// they both in
if ( (v1c!=outbit) && (v2c!=outbit))
poly2->vertices[poly2->numvertices++]=v2;
}
}
Now all you need is calculate the outcodes before entering the clipping routine.
"pin" is the polygon entered to the clipping. This example was done for triangles but you can do it for any number of points.
"pout" is simply the resulting polygon after the pin poly had been clipped.
calcoutcode(&pin.vertices[0]);
calcoutcode(&pin.vertices[1]);
calcoutcode(&pin.vertices[2]);
Clip against each plane at one time, use the result to clip against another plane, and so on.
clip(&pin, &pout, &Frustum[ 4 ], Near_Plane);
clip(&pout, &pin, &Frustum[ 0 ], Left_Plane);
clip(&pin, &pout, &Frustum[ 1 ], Right_Plane);
clip(&pout, &pin, &Frustum[ 2 ], Top_Plane);
clip(&pin, &pout, &Frustum[ 3 ], Bot_Plane);
All the clipping is done in 3d space (camera space). A good idea would be of course to clip in object space and not transform invisible vertices.
Now you just need to project and you have a perfectly clipped scene (I hope it's clear that there's no need to clip in 2d).
Some thoughts on optimizations
Now you have a working clipping. It's about time to add some speed to it. Let's start with a boundary sphere. A boundary sphere has two things:
1. Radius
2. Center point in the object
There are lots of ways to calculate boundary spheres. I will talk only about a few of them.
Calculating the radius could be done in object space where the center point of the b-sphere is (0,0,0) so basically you just go through all points and search for the biggest distance from the origin. In case you don't know,
distance = sqr(X^2+Y^2+Z^2)
assuming that point B is (X,Y,Z) and point A is (0,0,0).
Calculating the center of the object is quite easy. As I was told, the best method is to calculate a boundary box for the object and do the average point. This would give the center of the object, so:
centre.x = (MAXX+MINX)/2
centre.y = (MAXY+MINY)/2
centre.z = (MAXZ+MINZ)/2
MINX, MAXX, MINY,... are taken from the b-box. For more info on b-boxes check out frenzy's article in Hugi #16. Don't forget to check out Graphic Gems I (I think) for cool examples.
Boundary spheres are often used for collision detections between the object and the floor, walls, planes.
Checking collides between two spheres is also easy. It's just a matter of checking if the sum of their radiuses is bigger than the distance between their center point - then there's a collision detection.
Let's find out how to check whether the object intersects the plane, out of the plane or inside the plane.
We'll start with the case object is out of the plane. The "+" means it's the positive side of the plane where the "-" means it's the nagative side.
d - is the distance from the spheres centre to the plane.
r - is the radius of the sphere.
d
³
³ r
- ³ ³
³ ³
--------Á-----Á----------------- plane
+
From that we see:
if abs(d)>==r: The object is out of the plane (completely invisible).
if abs(d)<r: The object intersects the plane. You just need to use your imagination.
d = dot(plane_normal, centre_point) - plane_distance_from_origin;
It should be done in object space so you can save time of transforming invisible objects.
Tagging objects is very helpful. You have three tagging possibilites:
1. Object is invisible
2. Object intersects
3. Object is fully visible
You could also store another variable for telling against what planes the object should be clipped.
Creating the boundary box is even easier. A box should have 8 vertices but you've probably alredy known it.
Making a box is very simple. It reminds me of my electronics studies with boolean algebra for finding all possibilites. You change the frequency of the numbers by 2^n, where n is the column.
So, to generate numbers from 0-15 in base 2, you would have 3 columns:
n=3 n=2 n=1 n=0
D ³ C ³ B ³ A ³base 10
----³-----³-----³-----³--------
0 ³ 0 ³ 0 ³ 0 ³ 0
0 ³ 0 ³ 0 ³ 1 ³ 1
0 ³ 0 ³ 1 ³ 0 ³ 2
0 ³ 0 ³ 1 ³ 1 ³ 3
0 ³ 1 ³ 0 ³ 0 ³ 4
0 ³ 1 ³ 0 ³ 1 ³ 5
0 ³ 1 ³ 1 ³ 0 ³ 6
0 ³ 1 ³ 1 ³ 1 ³ 7
1 ³ 0 ³ 0 ³ 0 ³ 8
1 ³ 0 ³ 0 ³ 1 ³ 9
1 ³ 0 ³ 1 ³ 0 ³ 10
1 ³ 0 ³ 1 ³ 1 ³ 11
1 ³ 1 ³ 0 ³ 0 ³ 12
1 ³ 1 ³ 0 ³ 1 ³ 13
1 ³ 1 ³ 1 ³ 0 ³ 14
1 ³ 1 ³ 1 ³ 1 ³ 15
In column A we change from 0 to 1 and vice versa every step (2^0=1).
In column B we change from 0 to 1 and vice versa every 2 steps (2^1=2).
In column C we change from 0 to 1 and vice versa every 4 steps (2^2=4).
Well enough about old school stuff, in 3d we would have:
n=2 n=1 n=0
Z ³ Y ³ X ³ vertex number
------³------³------³-----------------
MINZ ³ MINY ³ MINX ³ 0
MINZ ³ MINY ³ MAXX ³ 1
MINZ ³ MAXY ³ MINX ³ 2
MINZ ³ MAXY ³ MAXX ³ 3
MAXZ ³ MINY ³ MINX ³ 4
MAXZ ³ MINY ³ MAXX ³ 5
MAXZ ³ MAXY ³ MINX ³ 6
MAXZ ³ MAXY ³ MAXX ³ 7
I'd better leave something you could do by yourself so if you have any troubles finding MINX, MAXX, MINY, MAXY, MINZ, MAXZ contact me.
You should first check whether the box is inside or outside the frustum:
If MINX is out of the right plane then it's out. If MAXX is out of the left plane then it's out. Do the same with MINY, MAXY, MINZ, MAXZ.
Tag whatever is needed, if it's neither of those then it's intersecting with some of the planes. Check which planes it intersects with, and draw it.
Collision detections with b-boxes
When each object has its own boundary box, you could do collision detection very easily with every object which has a boundary box. Basically we need a function which checks if a point is inside a b-box.
struct BBox {
Vector min, maxx;
Vector box[8];
};
bool PointInsideBox(BBox box, Vector point) {
return (point.x>box.min.x && point.x<box.max.x &&
point.y>box.min.y && point.y<box.max.y &&
point.z>box.min.z && point.y<box.max.z );
}
bool BoxCollide(BBox box1, BBox box2) {
return (PointInsideBox(box1, box2.min) ||
PointInsideBox(box1, box2.max));
}
I hope this works, I've written this part directly from my head after finishing writing the rasterization article, so this BoxCollide might not work. Actually most of the written stuff comes straight from my head.
Some basic stuff you should know
A vector is an arrow in space that has three components (x,y,z), it has a direction and length. When we're doing mathematical operations like DotProduct, CrossProduct, etc. the length is not important, as for instance a vector with the values (99999, 0, 0) has the same direction as a vector with the values (1, 0, 0).
DotProduct(V1, V2) = V1.x*V2.x + V1.y*V2.y + V1.z*V2.z;
The result of the DotProduct is a scalar (number without a direction), which is cosine(alpha), so by doing DotProduct on two vectors without any magnitude you can find out the cosine of the angle between those vectors.
CrossProduct(V1, V2) =
X = V1.y*V2.z - V1.z*V2.y;
Y = V1.z*V2.x - V1.x*V2.z;
Z = V1.x*V2.y - V1.y*V2.x;
The result of CrossProduct is a vector perpendicular to V1 and V2.
NormalizeVector(V) =
Length = V.x*V.x + V.y*V.y + V.z*V.z; // Taking the distance from
// the origin and the vector.
if (Length!=0) Length = 1.0 / sqrt(Length);
X = V.x*Length;
Y = V.y*Length;
Z = V.z*Length;
Just think about it. If you divide something by something bigger then the result is smaller than 1, like a/(a+1) is always -1<=result<=1, unit length of one.
A plane is a surface which can be made out of three points. It has a normal. A plane is infinite, i.e.: each normal points to infinity.
a, b, c are three points in space.
P1=(a-b)
P2=(a-c)
PlaneNormal = CrossProduct(P1, P2);
NormalizeVector(PlaneNormal);
A plane is defined as a normal and a distance to origin (x, y, z, distance).
Distance = the shortest distance from the plane to the origin.
The formula which describes the plane is:
Ax + By + Cz - D = 0
A = PlaneNormal.x
B = PlaneNormal.y
C = PlaneNormal.z
D = distance to the origin
So:
PointToOrigin = DotProduct(PlaneNormal, PointInSpace);
The result must not be from -1 to 1. DotProduct is used in many places, not only when the cos(angle) between two vectors is needed to be found.
The normals formula could be written as:
DotProduct(PlaneNormal, Point) - D = 0;
PointToPlane(Vector, Plane) = DotProduct(PlaneNormal, Point) - D;
If it's negative then it's on the negative side of the plane, if it's positive then it's on the positive side of the plane otherwise it's on the plane.
That's how backface culling is done: You form a plane out of your triangle, precalculate the distance from plane to origin in object space with
DotProduct(PlaneNormal, SomePointOnTriangle);
You inverse transform your camera back to object space and check the distance from point to
plane(triangle)
And
if (PointToPlane(camera, TriangleNormal)-PrecalculatedDistance)<0
then the triangle is invisible.
Greetz in random order
frenzy, kalms, sarwaz, salami, dvb, tnse^1999, altair, absent, macaw, greco, action, adept, submissive, kombat, sunday, katrikan, silvatar, tomh, mirek, vastator, nick-s, mrz, adok, velocity, v-man, coaxcable, sol_hsa, cube, yoyo, borzom, parody, graffik, attack, matja, vec, middy, silent breed, kutepixel, xerxes, c-bus, mali, midnight, scriptum, void, psychic sympony, ex, rodex, sagacity, raiden, gday, twobear, firedge, ravian, wog, xls, faktorii, shock, asm[exe], [ad]turbo, darkman, lnx, zoo-b, bacter, trashey, cycat, odin, radium, idiotboy.
Hot greetz to all Winter in July, Mistery, ZeroDefects members!!!!!
EFnet: #coders, #math
IRCNet: #pixel, #coders and #3dcoders of course